package com.localking.algorithm.leetcode.array

import scala.collection.mutable

/**
 * Given ans array of 2n integers, your task is to group theses integers into n pairs of integer, say(a1, b1), (a2, b2)...,(an, bn) which makes sum
 * of min(ai, bi) for all i from 1 to n as large as possible.
 *
 * Example 1:
 * Input: [1, 4, 3, 2]
 * Output: 4
 * Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
 *
 * Note:
 * 1. n is a positive integer, which is in the range of [1, 10000].
 * 2. All the integers in the array will be in the range of [-10000, 10000].
 *
 * @author jinbo
 */
object ArrayPairSum {
  def main(args: Array[String]): Unit = {
    val nums = Array(1, 4, 3, 2)
    println(arrayPairSum(nums))
  }

  def arrayPairSum(nums: Array[Int]): Int = {
    val occurTimesMap = mutable.Map[Int, Int]()
    for (num <- nums) {
      val occurTimes = occurTimesMap.getOrElse(num, 0)
      occurTimesMap.put(num, occurTimes + 1)
    }
    var single = false
    var sum = 0
    for (i <- -10000 to 10000) {
      val occurTimes = occurTimesMap.getOrElse(i, 0)
      if (occurTimes > 0) {
        val mod = occurTimes % 2
        if (mod == 0) {
          sum += occurTimes / 2 * i
        } else {
          if (single) {
            sum += occurTimes / 2 * i
          } else {
            sum += (occurTimes / 2 + 1) * i
          }
          single = !single
        }
      }
    }
    sum
  }
}
